Album phòng thu thứ ba của Muse là Absolution đã đem lại cho ban nhạc danh tiếng trong giới thính giả đại chúng tại Hoa Kỳ.[5] Muse bắt đầu sáng tác và tập luyện cho album kế tiếp tại Studio Miraval, một tòa lâu đài cổ tại Pháp. Nhà sản xuất cho Absolution là Rich Costey đã tham gia dự án cùng ban nhạc sau đó 2 tuần. Nhà sáng tác ca khúc Matt Bellamy cho biết nhóm muốn tránh bị phân tâm để họ có thể "tập trung, phân bổ thời gian và nằm trong nhiều luồng ảnh hưởng nhạc khác nhau". Tuy nhiên tiến độ làm album diễn ra chậm và họ gặp khó trong quyết định lựa chọn các ca khúc. Nhiều sản phẩm được hoàn thành tại hai xưởng thu Avatar Studios và Electric Lady Studios ở New York cũng như một xưởng thu tại Ý.

Cây bass của Muse, Christopher Wolstenholme cho biết quá trình sáng tác và thu âm cho Black Holes and Revelations thoải mái hơn so với những album trước vì cả nhóm không có hạn chót ấn định.[6] Costey muốn nắm lấy "cá tính" cầm thủ guitar của Muse nên đã ghi lại tiếng gảy đàn của anh. Đây còn là đầu tiên Muse dấn thân nghiên cứu về công nghệ trong phòng thu, việc mà trước đây họ để cho các kĩ thuật viên xử lý.[6] Khúc riff trong "Map of the Problematique" được sáng tác trên một chiếc đàn keyboard; với sự khích lệ từ Costey, Bellamy đã chơi lại khúc riff đó trên guitar bằng cách chia âm của nhạc cụ này thành ba dải sóng âm, được xử lý bởi máy chuyển cao độ và nhạc cụ synthesizer.

Bài "Soldier's Poem" được cho là "chẳng giống bất cứ thứ gì [Muse từng] làm trước đây".[7] Vốn được sáng tác cho Absolution, Matt đã sáng tác lại ca khúc để cho vào Black Holes với ca từ và phần chuyển soạn mới lấy cảm hứng từ bài "Can't Help Falling in Love" của Elvis Presley. Tay trống Dominic Howard cho biết nhóm nhạc từng định biến bài hát thành một "bản nhạc hùng tráng, mạnh mẽ" nhưng rồi quyết định sáng tác bằng cách dùng một phòng thu nhỏ với thiết bị cổ điển và một vài chiếc ống thu thanh.[7] Muse tỏ ra hài lòng với thành quả đạt được và Dom miêu tả "Soldier's Poem" như một "điểm sáng thực sự", với "chất giọng thuộc hàng ấn tượng nhất mà tôi từng nghe Matt thể hiện".[7]